#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

typedef struct TreeNode *Type;
typedef struct {
    Type *data;
    int size;
    int capacity;
} Stack;

void init(Stack *s)
{
    s->size = 0;
    s->capacity = 256;
    s->data = (Type *) malloc(s->capacity * sizeof(Type));
}

void destroy(Stack *s)
{
    s->size = 0;
    free(s->data);
}

void push(Stack *s, Type t)
{
    if (s->size == s->capacity) {
        Type *tmp = (Type *) malloc(2 * s->capacity * sizeof(Type));
        memcpy(tmp, s->data, s->capacity * sizeof(Type));
        free(s->data);
        s->data = tmp;
        s->capacity *= 2;
    }
    s->data[s->size++] = t;
}

Type pop(Stack *s)
{
    if (s->size == 0) {
        return NULL;
    }

    s->size--;
    return s->data[s->size];
}

bool isSameTree(struct TreeNode *p, struct TreeNode *q)
{
    bool result = true;
    Stack s;
    init(&s);

    push(&s, p);
    push(&s, q);

    while (s.size != 0) {
        Type a = pop(&s);
        Type b = pop(&s);

        if (a == NULL && b == NULL) {
            continue;
        } else if (a != NULL && b != NULL && a->val == b->val) {
            push(&s, a->left);
            push(&s, b->left);
            push(&s, a->right);
            push(&s, b->right);
        } else {
            result = false;
            break;
        }
    }

    destroy(&s);
    return result;
}

int main(int argc, char const *argv[])
{
    int a[] = { 0, -5 };
    int b[] = { 0, -8 };
    struct TreeNode al = {a[1], NULL, NULL};
    struct TreeNode bl = {b[1], NULL, NULL};
    struct TreeNode p = {a[0], &al, NULL};
    struct TreeNode q = {b[0], &bl, NULL};
    printf("%d\n", isSameTree(&p, &q));

    return 0;
}